{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Position for a Service Centre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #math #randomized"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数学 #随机化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMinDistSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #服务中心的最佳位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 <strong>到所有客户的欧几里得距离的总和最小</strong> 。</p>\n",
    "\n",
    "<p>给你一个数组 <code>positions</code> ，其中 <code>positions[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示第 <code>i</code> 个客户在二维地图上的位置，返回到所有客户的 <strong>欧几里得距离的最小总和 。</strong></p>\n",
    "\n",
    "<p>换句话说，请你为服务中心选址，该位置的坐标 <code>[x<sub>centre</sub>, y<sub>centre</sub>]</code> 需要使下面的公式取到最小值：</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/12/q4_edited.jpg\" /></p>\n",
    "\n",
    "<p>与真实值误差在 <code>10<sup>-5</sup></code>之内的答案将被视作正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/12/q4_e1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [[0,1],[1,0],[1,2],[2,1]]\n",
    "<strong>输出：</strong>4.00000\n",
    "<strong>解释：</strong>如图所示，你可以选 [x<sub>centre</sub>, y<sub>centre</sub>] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/12/q4_e3.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [[1,1],[3,3]]\n",
    "<strong>输出：</strong>2.82843\n",
    "<strong>解释：</strong>欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= positions.length &lt;= 50</code></li>\n",
    "\t<li><code>positions[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-position-for-a-service-centre](https://leetcode.cn/problems/best-position-for-a-service-centre/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-position-for-a-service-centre](https://leetcode.cn/problems/best-position-for-a-service-centre/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,0],[1,2],[2,1]]', '[[1,1],[3,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        eps, step = 1e-7, 1\n",
    "        n = len(positions)\n",
    "        x = sum(p[0] for p in positions) / n\n",
    "        y = sum(p[1] for p in positions) / n\n",
    "        cal = lambda p0: sum(dist(p0,p) for p in positions)\n",
    "        while step > eps:\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                x2,y2 = x+step*dx, y+step*dy\n",
    "                if cal((x2,y2))<cal((x,y)):\n",
    "                    x, y = x2, y2\n",
    "                    break\n",
    "            else:\n",
    "                step *= 0.5\n",
    "        return cal((x, y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        if len(positions) == 1:\n",
    "            return 0.0\n",
    "        xc, yc = mean([x for x, y in positions]), mean([y for x, y in positions])\n",
    "        step = 1.0\n",
    "        ans = 200 * 50\n",
    "        count = 0\n",
    "        while True:\n",
    "            tmp = 0.0\n",
    "            gx, gy = 0.0, 0.0\n",
    "            for x, y in positions:\n",
    "                d = sqrt((xc - x) ** 2 + (yc - y) ** 2)\n",
    "                tmp += d\n",
    "                if d > 1e-6:\n",
    "                    gx += (xc - x) / d\n",
    "                    gy += (yc - y) / d\n",
    "                else:\n",
    "                    gx += 1.0 if xc - x >= 0 else -1.0\n",
    "                    gy += 1.0 if yc - y >= 0 else -1.0\n",
    "            xc = xc - gx * step\n",
    "            yc = yc - gy * step\n",
    "            step *= 0.999\n",
    "            ans = min(ans, tmp)\n",
    "            count += 1\n",
    "            if count > 10000:\n",
    "                return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 三分查找\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        eps = 1e-7\n",
    "\n",
    "        # 计算服务中心 (xc, yc) 到客户的欧几里得距离之和\n",
    "        getDist = lambda xc, yc: sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x, y in positions)\n",
    "\n",
    "        # 固定 xc，使用三分法找出最优的 yc\n",
    "        def checkOptimal(xc: float) -> float:\n",
    "            yLeft, yRight = 0.0, 100.0\n",
    "            while yRight - yLeft > eps:\n",
    "                yFirst = (yLeft + yLeft + yRight) / 3\n",
    "                ySecond = (yLeft + yRight + yRight) / 3\n",
    "                if getDist(xc, yFirst) < getDist(xc, ySecond):\n",
    "                    yRight = ySecond\n",
    "                else:\n",
    "                    yLeft = yFirst\n",
    "            return getDist(xc, yLeft)\n",
    "        \n",
    "        xLeft, xRight = 0.0, 100.0\n",
    "        while xRight - xLeft > eps:\n",
    "            # 左 1/3 点\n",
    "            xFirst = (xLeft + xLeft + xRight) / 3\n",
    "            # 右 1/3 点\n",
    "            xSecond = (xLeft + xRight + xRight) / 3\n",
    "            if checkOptimal(xFirst) < checkOptimal(xSecond):\n",
    "                xRight = xSecond\n",
    "            else:\n",
    "                xLeft = xFirst\n",
    "\n",
    "        return checkOptimal(xLeft)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        n = len(positions)\n",
    "        x = y = 0\n",
    "        for x1, y1 in positions:\n",
    "            x += x1\n",
    "            y += y1\n",
    "        x, y = x / n, y / n\n",
    "        decay = .999\n",
    "        eps = 1e-6\n",
    "        alpha = .5\n",
    "        while 1:\n",
    "            grad_x = grad_y = 0\n",
    "            dist = 0\n",
    "            for x1, y1 in positions:\n",
    "                a = x - x1\n",
    "                b = y - y1\n",
    "                c = sqrt(a * a + b * b)\n",
    "                grad_x += a / (c + 1e-8)\n",
    "                grad_y += b / (c + 1e-8)\n",
    "                dist += c\n",
    "            dx = grad_x * alpha\n",
    "            dy = grad_y * alpha\n",
    "            x -= dx\n",
    "            y -= dy\n",
    "            alpha *= decay\n",
    "            if abs(dx) <= eps and abs(dy) <= eps:\n",
    "                return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        alpha = 1.0\n",
    "        decay = 1e-3\n",
    "        eps = 1e-7\n",
    "        n = len(positions)\n",
    "        x = sum([x for x,y in positions])/n\n",
    "        y = sum([y for x,y in positions])/n\n",
    "\n",
    "        getDist = lambda xc,yc: sum(((x-xc)**2+(y-yc)**2)**0.5 for x,y in positions)\n",
    "        batch_size = n\n",
    "        while True:\n",
    "            random.shuffle(positions)\n",
    "            xPrev, yPrev = x, y \n",
    "\n",
    "            for i in range(0,n,batch_size):\n",
    "                j = min(i + batch_size, n)\n",
    "                dx, dy = 0.0, 0.0\n",
    "\n",
    "                for k in range(i,j):\n",
    "                    pos = positions[k]\n",
    "                    dx += (x-pos[0])/(sqrt((x-pos[0])**2+(y-pos[1])**2)+eps)\n",
    "                    dy += (y-pos[1])/(sqrt((x-pos[0])**2+(y-pos[1])**2)+eps)\n",
    "                x -= alpha*dx\n",
    "                y -= alpha*dy\n",
    "                alpha*=(1.0-decay)\n",
    "            if ((x-xPrev)**2+(y-yPrev)**2)**0.5 < eps:\n",
    "                return getDist(x,y)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        eps = 1e-7\n",
    "        alpha = 1.0\n",
    "        decay = 1e-3\n",
    "\n",
    "        n = len(positions)\n",
    "        # 调整批大小\n",
    "        batchSize = n\n",
    "\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        \n",
    "        # 计算服务中心 (xc, yc) 到客户的欧几里得距离之和\n",
    "        getDist = lambda xc, yc: sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x, y in positions)\n",
    "        \n",
    "        while True:\n",
    "            # 将数据随机打乱\n",
    "            random.shuffle(positions)\n",
    "            xPrev, yPrev = x, y\n",
    "\n",
    "            for i in range(0, n, batchSize):\n",
    "                j = min(i + batchSize, n)\n",
    "                dx, dy = 0.0, 0.0\n",
    "\n",
    "                # 计算导数，注意处理分母为零的情况\n",
    "                for k in range(i, j):\n",
    "                    pos = positions[k]\n",
    "                    dx += (x - pos[0]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                    dy += (y - pos[1]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                \n",
    "                x -= alpha * dx\n",
    "                y -= alpha * dy\n",
    "\n",
    "                # 每一轮迭代后，将学习率进行衰减\n",
    "                alpha *= (1.0 - decay)\n",
    "            \n",
    "            # 判断是否结束迭代\n",
    "            if ((x - xPrev) ** 2 + (y - yPrev) ** 2) ** 0.5 < eps:\n",
    "                break\n",
    "\n",
    "        return getDist(x, y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        thr = 1e-5\n",
    "        decay = 0.999\n",
    "        # print(\"positions\", positions )\n",
    "        def gradient(x,y):\n",
    "            dx = 0\n",
    "            dy = 0\n",
    "            dist = 0\n",
    "            for a,b in positions:\n",
    "                S = ((a-x)**2 + (b-y)**2)**0.5\n",
    "                if S == 0:\n",
    "                    continue\n",
    "                dist += S\n",
    "                dx += -(a-x)/S\n",
    "                dy += -(b-y)/S\n",
    "\n",
    "            return dx, dy, dist\n",
    "\n",
    "        x = sum(x for x,y in positions) / len(positions)\n",
    "        y = sum(y for x,y in positions) / len(positions)\n",
    "        lr = 1\n",
    "        step = 1\n",
    "        while True:\n",
    "            \n",
    "            dx,dy, dist = gradient(x,y)\n",
    "            # print(step, \"x\",x,\"y\",y,\"dx\",dx,\"dy\",dy,\"dist\",dist, \"lr\",lr)\n",
    "            new_x = x - dx * lr\n",
    "            new_y = y - dy * lr\n",
    "\n",
    "            if (10*(new_x/10 - x/10) ** 2 + (new_y/10 - y/10)**2)**0.5 < 1e-7:\n",
    "                break\n",
    "            x = new_x\n",
    "            y = new_y\n",
    "            step += 1\n",
    "            lr *= decay\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        eps = 1e-7\n",
    "        alpha = 1.0\n",
    "        decay = 1e-3\n",
    "\n",
    "        n = len(positions)\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        def getDist(xc,yc):\n",
    "            return sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x,y in positions)\n",
    "        while True:\n",
    "            random.shuffle(positions)\n",
    "            xp,yp = x,y\n",
    "            dx,dy = 0.0,0.0\n",
    "            # eps 防止除数为 0 \n",
    "            for pos in positions:\n",
    "                dx += (x - pos[0]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                dy += (y - pos[1]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "            x -= alpha * dx\n",
    "            y -= alpha * dy\n",
    "            # 学习率衰减\n",
    "            alpha *= (1.0 - decay)\n",
    "            if ((x - xp) ** 2 + (y - yp) ** 2) ** 0.5 < eps:\n",
    "                break\n",
    "        return getDist(x,y)\n",
    "\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        N=len(positions)\n",
    "        x0 = sum([val[0] for i, val in enumerate(positions)])/N\n",
    "        y0 = sum([val[1] for i, val in enumerate(positions)])/N\n",
    "        if N>2:\n",
    "            iteration = 12000\n",
    "            x0 += random.random()\n",
    "            y0 += random.random()\n",
    "            pre_dist=float('inf')\n",
    "            err=1e-9\n",
    "            learning_rate = 1\n",
    "            for i in range(iteration):\n",
    "                grad_x = 0\n",
    "                grad_y = 0\n",
    "                \n",
    "                for val in positions:\n",
    "                    grad_x += (x0-val[0])/(math.sqrt((x0-val[0])**2+(y0-val[1])**2))\n",
    "                    grad_y += (y0-val[1])/(math.sqrt((x0-val[0])**2+(y0-val[1])**2))\n",
    "\n",
    "                x0 -= learning_rate*grad_x\n",
    "                y0 -= learning_rate*grad_y\n",
    "                dist = sum(((x0-val[0])**2+(y0-val[1])**2)**0.5 for val in positions)\n",
    "\n",
    "                if dist - pre_dist > 0:\n",
    "                    learning_rate *=0.5\n",
    "                if abs(dist - pre_dist) < err**2:\n",
    "                    break\n",
    "                pre_dist = dist\n",
    "        else:\n",
    "            dist = sum(((x0-val[0])**2+(y0-val[1])**2)**0.5 for val in positions)\n",
    "        \n",
    "\n",
    "\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 爬山法\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        eps = 1e-7\n",
    "        step = 1.0\n",
    "        decay = 0.5\n",
    "\n",
    "        n = len(positions)\n",
    "\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        \n",
    "        # 计算服务中心 (xc, yc) 到客户的欧几里得距离之和\n",
    "        getDist = lambda xc, yc: sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x, y in positions)\n",
    "        \n",
    "        while step > eps:\n",
    "            modified = False\n",
    "            for dx, dy in dirs:\n",
    "                xNext = x + step * dx\n",
    "                yNext = y + step * dy\n",
    "                if getDist(xNext, yNext) < getDist(x, y):\n",
    "                    x, y = xNext, yNext\n",
    "                    modified = True\n",
    "                    break\n",
    "            if not modified:\n",
    "                step *= (1.0 - decay)\n",
    "\n",
    "        return getDist(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        thr = 1e-5\n",
    "        decay = 0.999\n",
    "        # print(\"positions\", positions )\n",
    "        def gradient(x,y):\n",
    "            dx = 0\n",
    "            dy = 0\n",
    "            dist = 0\n",
    "            for a,b in positions:\n",
    "                S = ((a-x)**2 + (b-y)**2)**0.5\n",
    "                if S == 0:\n",
    "                    continue\n",
    "                dist += S\n",
    "                dx += -(a-x)/S\n",
    "                dy += -(b-y)/S\n",
    "\n",
    "            return dx, dy, dist\n",
    "\n",
    "        x = sum(x for x,y in positions) / len(positions)\n",
    "        y = sum(y for x,y in positions) / len(positions)\n",
    "        lr = 1\n",
    "        step = 1\n",
    "        while True:\n",
    "            \n",
    "            dx,dy, dist = gradient(x,y)\n",
    "            # print(step, \"x\",x,\"y\",y,\"dx\",dx,\"dy\",dy,\"dist\",dist, \"lr\",lr)\n",
    "            new_x = x - dx * lr\n",
    "            new_y = y - dy * lr\n",
    "\n",
    "            if (10*(new_x/10 - x/10) ** 2 + (new_y/10 - y/10)**2)**0.5 < 1e-7:\n",
    "                break\n",
    "            x = new_x\n",
    "            y = new_y\n",
    "            step += 1\n",
    "            lr *= decay\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 梯度下降\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        eps = 1e-7\n",
    "        alpha = 1.0\n",
    "        decay = 1e-3\n",
    "\n",
    "        n = len(positions)\n",
    "        # 调整批大小\n",
    "        batchSize = n\n",
    "\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        \n",
    "        # 计算服务中心 (xc, yc) 到客户的欧几里得距离之和\n",
    "        getDist = lambda xc, yc: sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x, y in positions)\n",
    "        \n",
    "        while True:\n",
    "            # 将数据随机打乱\n",
    "            random.shuffle(positions)\n",
    "            xPrev, yPrev = x, y\n",
    "\n",
    "            for i in range(0, n, batchSize):\n",
    "                j = min(i + batchSize, n)\n",
    "                dx, dy = 0.0, 0.0\n",
    "\n",
    "                # 计算导数，注意处理分母为零的情况\n",
    "                for k in range(i, j):\n",
    "                    pos = positions[k]\n",
    "                    dx += (x - pos[0]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                    dy += (y - pos[1]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                \n",
    "                x -= alpha * dx\n",
    "                y -= alpha * dy\n",
    "\n",
    "                # 每一轮迭代后，将学习率进行衰减\n",
    "                alpha *= (1.0 - decay)\n",
    "            \n",
    "            # 判断是否结束迭代\n",
    "            if ((x - xPrev) ** 2 + (y - yPrev) ** 2) ** 0.5 < eps:\n",
    "                break\n",
    "\n",
    "        return getDist(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        eps = 1e-7\n",
    "        alpha = 1.0\n",
    "        decay = 1e-3\n",
    "\n",
    "        n = len(positions)\n",
    "        # 调整批大小\n",
    "        batchSize = n\n",
    "\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        \n",
    "        # 计算服务中心 (xc, yc) 到客户的欧几里得距离之和\n",
    "        getDist = lambda xc, yc: sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x, y in positions)\n",
    "        \n",
    "        while True:\n",
    "            # 将数据随机打乱\n",
    "            random.shuffle(positions)\n",
    "            xPrev, yPrev = x, y\n",
    "\n",
    "            for i in range(0, n, n):\n",
    "                j = min(i + n, n)\n",
    "                dx, dy = 0.0, 0.0\n",
    "\n",
    "                # 计算导数，注意处理分母为零的情况\n",
    "                for k in range(i, j):\n",
    "                    pos = positions[k]\n",
    "                    dx += (x - pos[0]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                    dy += (y - pos[1]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)\n",
    "                \n",
    "                x -= alpha * dx\n",
    "                y -= alpha * dy\n",
    "\n",
    "                # 每一轮迭代后，将学习率进行衰减\n",
    "                alpha *= (1.0 - decay)\n",
    "            \n",
    "            # 判断是否结束迭代\n",
    "            if ((x - xPrev) ** 2 + (y - yPrev) ** 2) ** 0.5 < eps:\n",
    "                break\n",
    "\n",
    "        return getDist(x, y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        def getDist(xc, yc):\n",
    "            ans = 0\n",
    "            for x, y in positions:\n",
    "                ans += ((x - xc) ** 2 + (y - yc) ** 2) ** 0.5\n",
    "            return ans\n",
    "        eps = 1e-7\n",
    "        step = 1.0\n",
    "        decay = 0.5 \n",
    "        n = len(positions)\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        while step > eps:\n",
    "            flag = False\n",
    "            for dx, dy in (1,0),(-1,0),(0,1),(0,-1):\n",
    "                nx, ny = x + step * dx, y + step * dy\n",
    "                if getDist(nx, ny) < getDist(x, y):\n",
    "                    x, y = nx, ny\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                step *= (1.0 - decay)\n",
    "        return getDist(x, y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        n = len(positions)\n",
    "        x = y = 0\n",
    "        for x1, y1 in positions:\n",
    "            x += x1\n",
    "            y += y1\n",
    "        x, y = x / n, y / n\n",
    "        decay = .999\n",
    "        eps = 1e-6\n",
    "        alpha = .5\n",
    "        while 1:\n",
    "            grad_x = grad_y = 0\n",
    "            dist = 0\n",
    "            for x1, y1 in positions:\n",
    "                a = x - x1\n",
    "                b = y - y1\n",
    "                c = sqrt(a * a + b * b)\n",
    "                grad_x += a / (c + 1e-8)\n",
    "                grad_y += b / (c + 1e-8)\n",
    "                dist += c\n",
    "            dx = grad_x * alpha\n",
    "            dy = grad_y * alpha\n",
    "            x -= dx\n",
    "            y -= dy\n",
    "            alpha *= decay\n",
    "            if abs(dx) <= eps and abs(dy) <= eps:\n",
    "                return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        def getDist(xc, yc):\n",
    "            ans = 0\n",
    "            for x, y in positions:\n",
    "                ans += ((x - xc) ** 2 + (y - yc) ** 2) ** 0.5\n",
    "            return ans\n",
    "        eps = 1e-7\n",
    "        step = 1.0\n",
    "        decay = 1e-2\n",
    "        n = len(positions)\n",
    "        x = sum(pos[0] for pos in positions) / n\n",
    "        y = sum(pos[1] for pos in positions) / n\n",
    "        while step > eps:\n",
    "            flag = False\n",
    "            for dx, dy in (1,0),(-1,0),(0,1),(0,-1):\n",
    "                nx, ny = x + step * dx, y + step * dy\n",
    "                if getDist(nx, ny) < getDist(x, y):\n",
    "                    x, y = nx, ny\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                step *= (1.0 - decay)\n",
    "        return getDist(x, y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        alpha = 1.0\n",
    "        eps = 1e-7\n",
    "        decay = 1e-3\n",
    "        getDist = lambda xc, yc: sum(((x-xc)**2+(y-yc)**2)**0.5 for x, y in positions)\n",
    "        n = len(positions)\n",
    "        x = sum(x for x,y in positions)/n\n",
    "        y = sum(y for x,y in positions)/n\n",
    "        batch_size = n\n",
    "        while True:\n",
    "            random.shuffle(positions)\n",
    "            x_prev = x\n",
    "            y_prev = y\n",
    "            for i in range(0, n, batch_size):\n",
    "                j = min(i+batch_size, n)\n",
    "                dx, dy = 0.0, 0.0\n",
    "\n",
    "                for k in range(i,j):\n",
    "                    pos = positions[k]\n",
    "                    dx += (x-pos[0])/(sqrt((x-pos[0])**2+(y-pos[1])**2)+eps)\n",
    "                    dy += (y-pos[1])/(sqrt((x-pos[0])**2+(y-pos[1])**2)+eps)\n",
    "                x -= alpha*dx\n",
    "                y -= alpha*dy\n",
    "\n",
    "                alpha*=(1.0-decay)\n",
    "            if ((x-x_prev)**2+(y-y_prev)**2)**0.5 < eps:\n",
    "                return getDist(x,y)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        xmin, xmax, ymin, ymax = inf, -inf, inf, -inf\n",
    "        for i, j in positions:\n",
    "            xmin = min(xmin, i)\n",
    "            xmax = max(xmax, i)\n",
    "            ymin = min(ymin, j)\n",
    "            ymax = max(ymax, j)\n",
    "\n",
    "        @cache\n",
    "        def getdistance(x, y):\n",
    "            res = 0\n",
    "            for i, j in positions:\n",
    "                res += sqrt((i - x) ** 2 + (j - y) ** 2)\n",
    "            return res\n",
    "\n",
    "\n",
    "        while xmax - xmin > 1e-8 or ymax - ymin > 1e-8:\n",
    "            deltax = (xmax - xmin) / 20\n",
    "            deltay = (ymax - ymin) / 20\n",
    "            x = xmin\n",
    "            y = ymin\n",
    "            tx = xmin\n",
    "            ty = ymin\n",
    "            t = inf\n",
    "            for i in range(21):\n",
    "                for j in range(21):\n",
    "                    if getdistance(x + i * deltax, y + j * deltay) < t:\n",
    "                        tx = x + i * deltax\n",
    "                        ty = y + j * deltay\n",
    "                        t = getdistance(x + i * deltax, y + j * deltay)\n",
    "            xmin = tx - deltax\n",
    "            xmax = tx + deltax\n",
    "            ymin = ty - deltay\n",
    "            ymax = ty + deltay\n",
    "        return getdistance(xmin, ymin)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        from scipy.optimize import minimize\n",
    "        import math\n",
    "        return minimize(lambda t: sum([math.dist(p,t) for p in positions]),(0,0)).fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.optimize import minimize\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        return minimize(lambda t: sum([dist(p, t) for p in positions]), (0, 0))['fun']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        from scipy.optimize import minimize\n",
    "        n = len(positions)\n",
    "        x = sum(p[0] for p in positions) / n\n",
    "        y = sum(p[1] for p in positions) / n\n",
    "        cal = lambda p: sum(dist(p,p2) for p2 in positions)\n",
    "        return minimize(cal,(x,y)).fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        mx,my,n=0,0,len(positions)\n",
    "        for x,y in positions:\n",
    "            mx,my=mx+x,my+y\n",
    "        mx,my=mx/n,my/n\n",
    "        from scipy.optimize import minimize\n",
    "        import math\n",
    "        return minimize(lambda t: sum([math.dist(p,t) for p in positions]),(mx,my))['fun']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        from scipy.optimize import minimize\n",
    "        import math\n",
    "        return minimize(lambda t: sum([math.dist(p,t) for p in positions]),(0,0))['fun']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.optimize import minimize\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        def getSum(x):\n",
    "            return sum([sqrt((x[0] - x1) ** 2 + (x[1] - y1) ** 2) for x1, y1 in positions])\n",
    "        return minimize(getSum, [50, 50]).fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        from scipy.optimize import minimize\n",
    "        return minimize(lambda t: sum([dist(p,t) for p in positions]),(0,0))['fun']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.optimize import minimize\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        # print(minimize(lambda t: sum([dist(p, t) for p in positions]), (0, 0)))\n",
    "        # return 1.0\n",
    "        \n",
    "        return minimize(lambda t: sum([dist(p, t) for p in positions]), (0, 0))['fun']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinDistSum(self, positions: List[List[int]]) -> float:\n",
    "        from scipy.optimize import minimize\n",
    "        cal = lambda p: sum(dist(p,p2) for p2 in positions)\n",
    "        return minimize(cal,(0,0)).fun"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
